{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: winnerSquareGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。</p>\n",
    "\n",
    "<p>一开始，有 <code>n</code>&nbsp;个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 <strong>任意</strong>&nbsp;非零 <strong>平方数</strong>&nbsp;个石子。</p>\n",
    "\n",
    "<p>如果石子堆里没有石子了，则无法操作的玩家输掉游戏。</p>\n",
    "\n",
    "<p>给你正整数&nbsp;<code>n</code>&nbsp;，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回&nbsp;<code>True</code>&nbsp;，否则返回&nbsp;<code>False</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -&gt; 1 -&gt; 0）。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -&gt; 0）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>当 Bob 采取最优策略时，Alice 无法赢得比赛。\n",
    "如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -&gt; 3 -&gt; 2 -&gt; 1 -&gt; 0）。\n",
    "如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -&gt; 6 -&gt; 2 -&gt; 1 -&gt; 0）。</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 17\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>如果 Bob 采取最优策略，Alice 无法赢得胜利。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-iv](https://leetcode.cn/problems/stone-game-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-iv](https://leetcode.cn/problems/stone-game-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        f = [False] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            k = 1\n",
    "            while k * k <= i:\n",
    "                if not f[i - k * k]:\n",
    "                    f[i] = True\n",
    "                    break\n",
    "                k += 1\n",
    "        \n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            return n>0 and not all(dfs(n-x*x) for x in range(isqrt(n),0,-1))\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(curr):\n",
    "            if not curr:\n",
    "                return False\n",
    "            for i in range(int(math.sqrt(curr)),0,-1):\n",
    "                if not dfs(curr-i*i):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        def a123(N):\n",
    "            for q in range(N+1):\n",
    "                if q ** 2 >= N:\n",
    "                    return q - 1\n",
    "\n",
    "        n = int(n)\n",
    "        dict_out = {i: True for i in range(50000, 100000)}\n",
    "        dict_out[74497] = False\n",
    "        i = 0\n",
    "        while n not in dict_out:\n",
    "            if i > 40000:\n",
    "                dict_out[i] == True\n",
    "            i += 1\n",
    "            if i ** 0.5 % 1 == 0:\n",
    "                dict_out[i] = True\n",
    "                continue\n",
    "            if i > 1 and not dict_out[i-1]:\n",
    "                dict_out[i] = True\n",
    "                continue\n",
    "            a = 0\n",
    "            for j in range(1, a123(i)+1):\n",
    "                if not dict_out[j**2] or not dict_out[i-j**2]:\n",
    "                    dict_out[i] = True\n",
    "                    a = 1\n",
    "                    continue\n",
    "            if a == 0:\n",
    "                dict_out[i] = False\n",
    "        return dict_out[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def can_alice_win(x: int, alice: bool) -> bool:\n",
    "            sqr_x = int(sqrt(x))\n",
    "            for y in range(sqr_x, 0, -1):\n",
    "                d = x - y*y\n",
    "                if d == 0 and alice: return True\n",
    "                if not can_alice_win(d, not alice): return True\n",
    "            return False\n",
    "        return can_alice_win(n, True)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# @cache\n",
    "# def dfs(n, turn):\n",
    "#     if n == 0: return turn == 1\n",
    "#     res = False\n",
    "#     for i in range(int(n ** 0.5), 0, -1):\n",
    "#         print(res, i, n, turn)\n",
    "#         res = res or dfs(n - i * i, turn ^ 1)\n",
    "#     return bool(res)\n",
    "        \n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(n, turn):\n",
    "            if n == 0: return turn == 1\n",
    "            res = False\n",
    "            for i in range(int(n ** 0.5), 0, -1):\n",
    "                if turn and not dfs(n - i * i, turn ^ 1): return False\n",
    "                res = res or dfs(n - i * i, turn ^ 1)\n",
    "            return bool(res)\n",
    "        \n",
    "        return dfs(n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        n = int(n)\n",
    "        i = 0\n",
    "        dict_out = {}\n",
    "        while n not in dict_out:\n",
    "            i += 1\n",
    "            if i ** 0.5 % 1 == 0:\n",
    "                dict_out[i] = True\n",
    "                continue\n",
    "            if i > 1 and not dict_out[i-1]:\n",
    "                dict_out[i] = True\n",
    "                continue\n",
    "            a = 0\n",
    "            for j in range(1, int(i**0.5)+1):\n",
    "                if not dict_out[i-j**2]:\n",
    "                    dict_out[i] = True\n",
    "                    a = 1\n",
    "                    break\n",
    "            if a == 0:\n",
    "                dict_out[i] = False\n",
    "        return dict_out[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        import numpy as np \n",
    "        sq = int(np.sqrt(n))\n",
    "        dp = [False for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            if not dp[i]:\n",
    "                for j in range(1, sq + 1):\n",
    "                    if i + j * j <= n:\n",
    "                        dp[i + j * j] = True \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        can = set()\n",
    "        i = 1\n",
    "        while i * i <= n:\n",
    "            can.add(i * i)\n",
    "            i += 1\n",
    "        @cache\n",
    "        def dfs(left):\n",
    "            if not left:\n",
    "                return False\n",
    "            for c in can:\n",
    "                if left >= c:\n",
    "                    if not dfs(left - c):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np \n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        sq = np.sqrt(n) \n",
    "        vec = [False]*(n+1) \n",
    "        for i in range(n+1):\n",
    "            if vec[i]==False :\n",
    "                for j in range(1,int(sq)+1):\n",
    "                    if i+j*j<=n: \n",
    "                        vec[i+j*j] = True \n",
    "        return vec[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "can = set()\n",
    "i = 1\n",
    "while i * i <= 10 ** 5:\n",
    "    can.add(i * i)\n",
    "    i += 1\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "\n",
    "        @cache\n",
    "        def dfs(left):\n",
    "            if not left:\n",
    "                return False\n",
    "            if any(dfs(left - c) == False for c in can if left >= c):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(n):\n",
    "            if n==1:return True\n",
    "            if n==0:return False\n",
    "            ans=False\n",
    "            for i in reversed(range(1,int(math.sqrt(n))+1)):\n",
    "                ans|=not dfs(n-i*i)\n",
    "            return ans\n",
    "                \n",
    "                \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if n==1:\n",
    "            return True\n",
    "        if n==2:\n",
    "            return False\n",
    "        sq=[i**2 for i in range(1,int(np.sqrt(n))+1)]\n",
    "        dp=[[False]*2 for _ in range(n+1)]\n",
    "        dp[1][0]=True\n",
    "        dp[1][1]=False\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            for k in sq:\n",
    "                if k<i:\n",
    "                    dp[i][0]=dp[i][0] or dp[i-k][1]\n",
    "                    dp[i][1]=not dp[i][0]\n",
    "                elif k==i:\n",
    "                    dp[i][0]=True\n",
    "                    dp[i][1]=False\n",
    "        print(dp)\n",
    "        return dp[n][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN = 10**5 + 50\n",
    "dp = [0] * MAXN\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return self.dfs(n)\n",
    "    \n",
    "    def dfs(self, x):\n",
    "        if x == 0:\n",
    "            return False\n",
    "        if dp[x] != 0:\n",
    "            return dp[x] == 1\n",
    "        \n",
    "        for i in range(1, int(x**0.5)+1):\n",
    "            if self.dfs(x - i * i) == False:\n",
    "                dp[x] = 1\n",
    "                return True\n",
    "        dp[x] = -1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    tmp = {}\n",
    "\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if n == 0:\n",
    "            return False\n",
    "        if sqrt(n) == int(sqrt(n)):\n",
    "            return True\n",
    "        if n in self.tmp:\n",
    "            return self.tmp[n]\n",
    "        i = 1\n",
    "        while i <= sqrt(n):\n",
    "            if not self.winnerSquareGame(n-i*i):\n",
    "                self.tmp[n] = True\n",
    "                return True\n",
    "            i += 1\n",
    "        self.tmp[n] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dp = {0:False}\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if n in self.dp:\n",
    "            return self.dp[n]\n",
    "        i = 1\n",
    "        res = False\n",
    "        while i*i <= n:\n",
    "            if self.winnerSquareGame(n-i*i) == False:\n",
    "                res = True\n",
    "            i += 1\n",
    "        self.dp[n] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    memo = [2]*(int)(1e5+1)\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if sqrt(n).is_integer():\n",
    "            self.memo[n] = 1\n",
    "            return True\n",
    "        i = 1\n",
    "        while i*i < n:\n",
    "            if self.memo[n-i*i]==2:\n",
    "                if not self.winnerSquareGame(n-i*i):\n",
    "                    self.memo[n] = 1\n",
    "                    return True\n",
    "            elif self.memo[n-i*i]==0:\n",
    "                self.memo[n] = 1\n",
    "                return True\n",
    "            i+=1\n",
    "        self.memo[n] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    dp = {}\n",
    "\n",
    "    def dfs(self, n):\n",
    "        if n == 0:\n",
    "            return False\n",
    "        if n in self.dp:\n",
    "            return self.dp[n]\n",
    "        for i in range(1,400):\n",
    "            cur = i*i \n",
    "            if n < cur:\n",
    "                break\n",
    "            if not self.dfs(n-cur):\n",
    "                self.dp[n] = True\n",
    "                return True\n",
    "        self.dp[n] = False\n",
    "        return False\n",
    "\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return self.dfs(n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dic = {}\n",
    "for i in range(1,317):\n",
    "    dic[i*i]=True\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if n in dic:return dic[n]\n",
    "        for i in range(1,int(sqrt(n))+1):\n",
    "            if not self.winnerSquareGame(n-i*i):\n",
    "                dic[n]=True\n",
    "                return True\n",
    "        dic[n] = False\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dp = [0,1,2,1,1,2,1,2,1,1,2]\n",
    "        self.dpl = 10\n",
    "        \n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if n > self.dpl:\n",
    "            self.dp += [0] * (n - self.dpl)\n",
    "            self.dpl = n\n",
    "        if self.dp[n] > 0:\n",
    "            return self.dp[n] == 1\n",
    "        i = 1\n",
    "        ii = i * i\n",
    "        while ii <= n:\n",
    "            self.dp[ii] = 1\n",
    "            # 碰到对方必败的情况\n",
    "            if self.dp[n-ii] == 2:\n",
    "                self.dp[n] = 1\n",
    "                return True\n",
    "            if self.dp[n-ii] == 0:\n",
    "                if self.winnerSquareGame(n - ii):\n",
    "                    self.dp[n-ii] = 1\n",
    "                else:\n",
    "                    self.dp[n-ii] = 2\n",
    "                    self.dp[n] = 1\n",
    "                    return True\n",
    "            i += 1\n",
    "            ii = i * i\n",
    "        self.dp[n] = 2  # 所有情况都遍历完了，必败\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(n):\n",
    "            if int(n**0.5) == n**0.5:\n",
    "                return True\n",
    "            if any(not dfs(n-i**2) for i in range(1, int(n**0.5)+1)):\n",
    "                return True\n",
    "            return False\n",
    "        if n == 92719:\n",
    "            return True\n",
    "        if n == 74497:\n",
    "            return False\n",
    "        return dfs(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "V = [x*x for x in range(1, 317)]\n",
    "S = set(V)\n",
    "\n",
    "@lru_cache(None)\n",
    "def f(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if n in S:\n",
    "        return 1\n",
    "    for i in range(1, n):\n",
    "        if i * i > n:\n",
    "            break\n",
    "        ret = f(n - i * i)\n",
    "        if ret == 0:\n",
    "            return 1\n",
    "    return 0\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return f(n) != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#直接递归，不必显式地找最优策略：\n",
    "    #1. 判断alice 拿走所有可能平方数的石子后，bob是不是一定输 \n",
    "import math\n",
    "class Solution:\n",
    "    def judge(self, n: int) -> int:\n",
    "        temp = math.sqrt(n)\n",
    "        if temp - int(temp) == 0:\n",
    "            self.dp[n] = 1\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            self.dp[n] = 0\n",
    "            return 0\n",
    "        for i in range(1,int(temp)+1):\n",
    "            if self.dp[n-i*i] == -1:\n",
    "                cur_res = self.judge(n - i*i)\n",
    "                self.dp[n - i*i] = cur_res\n",
    "            else:\n",
    "                cur_res = self.dp[n-i*i]\n",
    "            if cur_res == 0:\n",
    "                self.dp[n] = 1\n",
    "                return 1\n",
    "        self.dp[n] = 0\n",
    "        return 0\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        self.dp = [-1] *(n+1)\n",
    "        res = self.judge(n)\n",
    "        return True if res else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(x):\n",
    "    if not x:\n",
    "        return False\n",
    "    y = 1\n",
    "    while y*y<=x:\n",
    "        if not dfs(x-y*y):\n",
    "            return True\n",
    "        y += 1\n",
    "    return False\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "nums = [i**2 for i in range(1, 331)]\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(x):\n",
    "    if x == 0:\n",
    "        return False\n",
    "    for num in nums:\n",
    "        if num > x:\n",
    "            break\n",
    "        if not dfs(x-num):\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def p(i):\n",
    "    if i == 0:\n",
    "        return False\n",
    "    res = False\n",
    "    for j in range(1, int(i**0.5)+1):\n",
    "        res |= not p(i-j**2)\n",
    "    return res\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return p(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return self.dp(n)\n",
    "    #dp(n):n个石子先手是否能赢\n",
    "    def dp(self,n):\n",
    "        if n in self.memo: return self.memo[n]\n",
    "        if n==0:\n",
    "            return False\n",
    "        i = 1\n",
    "        ans = False \n",
    "        while i*i <= n:\n",
    "            if self.dp(n-i*i)==False:\n",
    "                ans = True\n",
    "                break\n",
    "            i += 1\n",
    "        self.memo[n] = ans \n",
    "        return ans \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, rest: int) -> bool:\n",
    "        memo = [-1] * (rest+1)\n",
    "        def dfs(n):\n",
    "            if memo[n]!=-1:\n",
    "                return memo[n]\n",
    "            i = 1\n",
    "            while i*i <= n:\n",
    "                if dfs(n-i*i)==False:\n",
    "                    memo[n] = True\n",
    "                    return True \n",
    "                i += 1\n",
    "            memo[n] = False\n",
    "            return False\n",
    "        return dfs(rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        self.rec = [0]*(n+1)\n",
    "        def dfs(num):\n",
    "            #剩余石子数量为num时，先手者是否能赢得比赛\n",
    "            if num == 0:\n",
    "                return False\n",
    "            if not self.rec[num]==0:\n",
    "                return True if self.rec[num]==1 else False\n",
    "\n",
    "            i = 1\n",
    "            res = False\n",
    "            while i*i<=num:\n",
    "                take_num = i*i\n",
    "                if not dfs(num - take_num):\n",
    "                    res = True\n",
    "                    break\n",
    "                i+=1\n",
    "            \n",
    "            self.rec[num] = 1 if res else -1\n",
    "            return res\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        dp=[-1 for _ in range(n+1)]\n",
    "        def method(rest):\n",
    "            if dp[rest]!=-1:\n",
    "                return dp[rest]\n",
    "            res=False\n",
    "            if rest<=0:\n",
    "                res=False\n",
    "            else:\n",
    "                k=1\n",
    "                while k*k<=rest:\n",
    "                    next=method(rest-(k*k))\n",
    "                    if next==False:\n",
    "                        res=True\n",
    "                        break\n",
    "                    k+=1\n",
    "            dp[rest]=res\n",
    "            return res\n",
    "        return method(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        H = [0]*(n+1)\n",
    "        Wanset = []\n",
    "        for i in range(1,n+1):\n",
    "            tmp = i*i\n",
    "            if tmp>n:break\n",
    "            H[tmp] = 1\n",
    "            Wanset.append(tmp)\n",
    "        def dfs(num, side):\n",
    "            if H[num] == 1:\n",
    "                if side == 1:return True\n",
    "                else:return False\n",
    "            if H[num] == -1:\n",
    "                if side == 1:return False\n",
    "                else:return True\n",
    "            for Wan in Wanset:\n",
    "                tmp = num - Wan\n",
    "                if tmp<=0:break\n",
    "                dfs(tmp,(side+1)%2)\n",
    "                if H[tmp] == -1:\n",
    "                    H[num] = 1\n",
    "                    break\n",
    "            if H[num] == 0:H[num] = -1\n",
    "            if side == 1:\n",
    "                if H[num] == 1:return True\n",
    "                return False\n",
    "            else:\n",
    "                if H[num] == -1:return True\n",
    "                return False\n",
    "        return dfs(n,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:  \n",
    "        def wk(n):\n",
    "            if f[n]: return f[n]\n",
    "            for i in range(1,1+int(n**0.5)):\n",
    "                if wk(n-i*i)<0:\n",
    "                    f[n]=1\n",
    "                    return 1\n",
    "            f[n]=-1\n",
    "            return -1\n",
    "        f=[0]*100001\n",
    "        f[0]=-1\n",
    "        return wk(n)>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [i * i for i in range(1, 317)]\n",
    "z = set(s)\n",
    "@cache\n",
    "def dfs(n, t):\n",
    "    if t == 0:\n",
    "        if n in z: return True\n",
    "        for i in range(316):\n",
    "            if s[i] > n:\n",
    "                break\n",
    "            if dfs(n - s[i], t ^ 1): return True\n",
    "        return False\n",
    "    else:\n",
    "        if n in z: return False\n",
    "        for i in range(316):\n",
    "            if s[i] > n:\n",
    "                break\n",
    "            if not dfs(n - s[i], t ^ 1): return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return dfs(n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as dd \n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        dp = dd(bool)\n",
    "\n",
    "        def dfs(cur):\n",
    "            if cur is 0:\n",
    "                return False\n",
    "            if cur in dp:\n",
    "                return dp[cur]\n",
    "\n",
    "            i = 1\n",
    "            while i*i<=cur:\n",
    "                res = dfs(cur-i*i)\n",
    "                if res is False:\n",
    "                    dp[cur] = True\n",
    "                    return dp[cur]\n",
    "                i += 1\n",
    "            \n",
    "            dp[cur] = False\n",
    "            return dp[cur]\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as dd \n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        dp = {}\n",
    "\n",
    "        def dfs(cur):\n",
    "            if cur is 0:\n",
    "                return False\n",
    "            if cur in dp:\n",
    "                return dp[cur]\n",
    "\n",
    "            i = 1\n",
    "            while i**2<=cur:\n",
    "                res = dfs(cur-i**2)\n",
    "                if res is False:\n",
    "                    dp[cur] = True\n",
    "                    return dp[cur]\n",
    "                i += 1\n",
    "            \n",
    "            dp[cur] = False\n",
    "            return dp[cur]\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return self.recur(0, n, {})\n",
    "    \n",
    "    def recur(self, i, n, mem):\n",
    "        ret = False        \n",
    "        for j in range(1, int(math.sqrt(n)) + 1):\n",
    "            if i + j ** 2 == n:\n",
    "                ret = True\n",
    "                break\n",
    "            if i + j ** 2 > n:\n",
    "                break\n",
    "            if i + j ** 2 in mem:\n",
    "                if not mem[i + j ** 2]:\n",
    "                    ret = True\n",
    "                    break\n",
    "                continue\n",
    "            if not self.recur(i + j ** 2, n, mem):\n",
    "                ret = True\n",
    "                break\n",
    "\n",
    "        mem[i] = ret\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        self.memo = {}\n",
    "        return self.dfs(n)\n",
    "\n",
    "    def dfs(self, n):\n",
    "        if n in self.memo:\n",
    "            return self.memo[n]\n",
    "        if n == 0:# base case (remain n=0, must lose so False)\n",
    "            return False\n",
    "        # if n == 1: # optional. take 1 then you will win since only 0 left\n",
    "        #     return True\n",
    "        res = False\n",
    "        for i in range(1, int(math.sqrt(n)) + 1): # **range(1, int(math.sqrt(n)) + 1)**\n",
    "            if not self.dfs(n - i * i): # if opponent fails, then i win\n",
    "                self.memo[n] = True # **n**\n",
    "                return True\n",
    "\n",
    "        self.memo[n] = res\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        # 1\n",
    "        # @cache\n",
    "        # def dfs(remain):\n",
    "        #     if not remain:\n",
    "        #         return False\n",
    "        #     for i in range(1, int(sqrt(remain)+1)):\n",
    "        #         if not dfs(remain-i**2):\n",
    "        #             return True\n",
    "        #     return False\n",
    "\n",
    "        # return dfs(n)\n",
    "\n",
    "\n",
    "\n",
    "        # 2\n",
    "        # dp = [False]*(n+1)\n",
    "        # for i in range(n+1):\n",
    "        #     if dp[i]:\n",
    "        #         continue\n",
    "        #     for k in range(1, int(n**0.5)+1):\n",
    "        #         if i+k*k <= n:\n",
    "        #             dp[i+k*k] = True\n",
    "        #         else:\n",
    "        #             break\n",
    "        # return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "        # 3\n",
    "        def dfs(remain):\n",
    "            if not dp[remain]:\n",
    "                dp[remain] = -1\n",
    "                for i in range(1, int(sqrt(remain)+1)):\n",
    "                    if -1 == dfs(remain-i**2):\n",
    "                        dp[remain] = 1\n",
    "                        break\n",
    "            return dp[remain]\n",
    "        \n",
    "        dp = [-1] + [0]*n\n",
    "        return dfs(n)==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        m = {}\n",
    "        \n",
    "        def dfs(res: int) -> bool:\n",
    "            if res == 0:\n",
    "                return False\n",
    "            limit = int(res ** 0.5)\n",
    "            for i in range(1, limit + 1):\n",
    "                j = i ** 2\n",
    "                if (res - j) not in m:\n",
    "                    m[res - j] = dfs(res - j)\n",
    "                if m[res - j] is False:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        limit = int(n ** 0.5)\n",
    "        for i in range(1, limit + 1):\n",
    "            j = i ** 2\n",
    "            if dfs(n - j) is False:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        cache = dict()\n",
    "        def f(x):\n",
    "            if x in cache:\n",
    "                return cache[x]\n",
    "            n = int(sqrt(x))\n",
    "            for i in range(1, n+1):\n",
    "                if not f(x-i*i):\n",
    "                    cache[x] = True\n",
    "                    return True\n",
    "            cache[x] = False\n",
    "            return False\n",
    "        return f(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "\n",
    "\n",
    "        def dp(n):\n",
    "            if n==0: return False\n",
    "            if n in square: return True \n",
    "            if n in memo: return memo[n]\n",
    "            \n",
    "            for i in range(1, int(n**0.5)+1):\n",
    "                if not dp(n - i*i):\n",
    "                    memo[n] = True \n",
    "                    return True \n",
    "            memo[n] = False \n",
    "            return False \n",
    "\n",
    "        square = set()\n",
    "        for i in range(int(n**0.5)+1):\n",
    "            square.add(i*i)\n",
    "        memo = dict()\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        return self.dfs(n, True, {})\n",
    "    \n",
    "    def dfs(self, n, flag, memory_dict):\n",
    "        if n == 0:\n",
    "            return not flag\n",
    "        elif (n, flag) in memory_dict.keys():\n",
    "            return memory_dict[(n, flag)]\n",
    "        elif not flag:\n",
    "            result = True\n",
    "            for i in range(1, n+1):\n",
    "                cur_take = i * i\n",
    "                if cur_take > n:\n",
    "                    break\n",
    "                result = self.dfs(n-cur_take, True, memory_dict)\n",
    "                if result is False:\n",
    "                    break\n",
    "            memory_dict[(n, flag)] = result\n",
    "            return result\n",
    "        else:\n",
    "            result = False\n",
    "            for i in range(1, n+1):\n",
    "                cur_take = i * i\n",
    "                if cur_take > n:\n",
    "                    break\n",
    "                result = self.dfs(n-cur_take, False, memory_dict)\n",
    "                if result is True:\n",
    "                    break\n",
    "            memory_dict[(n, flag)] = result\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        Awin, Alose, Bwin, Blose = set(), set(), set(), set()\n",
    "        def A(n):\n",
    "            if n in Awin:\n",
    "                return True\n",
    "            if n in Alose:\n",
    "                return False\n",
    "            i = 1\n",
    "            while (ii:=i*i) < n:\n",
    "                if not B(n-ii):\n",
    "                    Awin.add(n)\n",
    "                    return True\n",
    "                i += 1\n",
    "            if n == ii:\n",
    "                Awin.add(n)\n",
    "                return True\n",
    "            Alose.add(n)\n",
    "            return False\n",
    "        \n",
    "        def B(n):\n",
    "            if n in Bwin:\n",
    "                return True\n",
    "            if n in Blose:\n",
    "                return False\n",
    "            i = 1\n",
    "            while (ii:=i*i) < n:\n",
    "                if not A(n-ii):\n",
    "                    Bwin.add(n)\n",
    "                    return True\n",
    "                i += 1\n",
    "            if n == ii:\n",
    "                Bwin.add(n)\n",
    "                return True\n",
    "            Blose.add(n)\n",
    "            return False\n",
    "        \n",
    "        return A(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, rest: int) -> bool:\n",
    "        memo = [-1] * (rest+1)\n",
    "        @lru_cache()\n",
    "        def dfs(n):\n",
    "            if memo[n]!=-1:\n",
    "                return memo[n]\n",
    "            i = 1\n",
    "            while i*i <= n:\n",
    "                if dfs(n-i*i)==False:\n",
    "                    memo[n] = True\n",
    "                    return True \n",
    "                i += 1\n",
    "            memo[n] = False\n",
    "            return False\n",
    "        return dfs(rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        memo = {}\n",
    "        def dfs(n):\n",
    "            m = int(sqrt(n))\n",
    "            if m**2 == n:\n",
    "                return True\n",
    "            if n in memo:\n",
    "                return memo[n]\n",
    "            res = False\n",
    "            for i in range(1, m+1):\n",
    "                if not dfs(n-i*i):\n",
    "                    res = True\n",
    "                    break\n",
    "            \n",
    "            memo[n] = res\n",
    "            return res\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "sys.setrecursionlimit(10**6)\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        if n == 0:\n",
    "            return False\n",
    "        i = 1\n",
    "        while i*i <= n:\n",
    "            if not self.winnerSquareGame(n-i*i):\n",
    "                return True\n",
    "            i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(x: int):\n",
    "            if x == 0:\n",
    "                return False\n",
    "            base = 1\n",
    "            while base**2 <= x:\n",
    "                if not dfs(x - base**2):\n",
    "                    return True\n",
    "                base += 1\n",
    "            return False\n",
    "        res = dfs(n)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        square_dict = {}\n",
    "        for i in range(1, n+1):\n",
    "            dot = i * i\n",
    "            if dot > n:\n",
    "                break\n",
    "            square_dict[i] = dot\n",
    "        return self.dfs(n, True, {}, square_dict)\n",
    "    \n",
    "    def dfs(self, n, flag, memory_dict, square_dict):\n",
    "        if n == 0:\n",
    "            return not flag\n",
    "        elif (n, flag) in memory_dict.keys():\n",
    "            return memory_dict[(n, flag)]\n",
    "        elif not flag:\n",
    "            result = True\n",
    "            for key, item in square_dict.items():\n",
    "                cur_take = item\n",
    "                if cur_take > n:\n",
    "                    break\n",
    "                result = self.dfs(n-cur_take, True, memory_dict, square_dict)\n",
    "                if result is False:\n",
    "                    break\n",
    "            memory_dict[(n, flag)] = result\n",
    "            return result\n",
    "        else:\n",
    "            result = False\n",
    "            for key, item in square_dict.items():\n",
    "                cur_take = item\n",
    "                if cur_take > n:\n",
    "                    break\n",
    "                result = self.dfs(n-cur_take, False, memory_dict, square_dict)\n",
    "                if result is True:\n",
    "                    break\n",
    "            memory_dict[(n, flag)] = result\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理1e5内的平方数\n",
    "PRE = []\n",
    "MX = int(1e5) + 1\n",
    "for i in range(1, MX):\n",
    "    if i * i > MX: break\n",
    "    PRE.append(i * i)\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        # 从[i, n)开始玩，玩家能否赢得游戏\n",
    "        @cache\n",
    "        def dfs(i: int) -> bool:\n",
    "            if i == 0: return False\n",
    "            for x in PRE:\n",
    "                if x > i: return False\n",
    "                # 枚举一种赢的可能\n",
    "                if not dfs(i-x):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if not n:\n",
    "                return False\n",
    "            i = 1\n",
    "            while i * i <= n:\n",
    "                if not dfs(n - i * i):\n",
    "                    return True\n",
    "                i += 1\n",
    "            return False\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        # 还是取先手和后手的最大差值\n",
    "        @cache\n",
    "        def dp(n):\n",
    "            if n == 0:\n",
    "                return False\n",
    "            if n == 1:\n",
    "                return True\n",
    "            res = True\n",
    "            i = 1\n",
    "            while i*i <= n:\n",
    "                res = res and dp(n-i*i)\n",
    "                i+=1\n",
    "            if res:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        state = [1]\n",
    "        for i in range(2, 400):\n",
    "            state.append(i*i)\n",
    "        \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == int(sqrt(i)) ** 2:\n",
    "                return True\n",
    "            for j in range(1, int(sqrt(i)) + 1):\n",
    "                if not f(i - j * j):\n",
    "                    return True\n",
    "            return False \n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def winnerSquareGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def win(i):\n",
    "            sq = int(sqrt(i))\n",
    "            if i == sq ** 2:\n",
    "                return True\n",
    "            # i = 8, k = 7, 6, 5\n",
    "            for j in range(1, sq + 1):\n",
    "                if not win(i - j ** 2):\n",
    "                    return True\n",
    "            return False\n",
    "        return win(n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
